package wangn.procedure;

import wangn.adt.CFG;
import wangn.adt.base.More;
import wangn.adt.base.Pair;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *FOLLOW用在求规约的时候
 * 步骤：
 * 一、首先由cfg第一条知道开始符S
 * 二、若求FOLLOW(S)返回$即可
 * 三、遍历cfg，查找所有G->aXb，且
 * 四、若b不为空，则求p=FIRST（b），若p有%则p删除%再求FOLLOW(G)否则不求，然后p放入follow(X)中
 * 五、若b为空，则直接求FOLLOW(G)
 */
public class FOLLOW {

    private static CFG cfg;
    private static char start;

    private static Set<Character> visitedCharSet = new HashSet<>();

    /**
     *
     * @param cfgIn 扩增文法
     * @param x 产生式的左部
     * @return 产生式的序号以及对应的FOLLOW集合
     */
    public static Pair<Integer,More<Character>> follow(CFG cfgIn, String x){
        cfg = cfgIn;
        visitedCharSet.clear();
        start = cfg.getGrammar(1).getFirst().charAt(0);
        More<Character> more = follow(x.charAt(0));
        return new Pair<>(0,more);
    }

    private static More<Character> follow(char x){
        More<Character> more = new More<>();
        if (visitedCharSet.contains(x))return more;
        visitedCharSet.add(x);
        int length = cfg.getLength();
        int i = 0;
        while (i <length){
            String rightGrammar = cfg.getGrammar(i).getSecond();
            for (int j = 0; j < rightGrammar.length(); j++){
                if (rightGrammar.charAt(j) == x){
                    More<Character> tmpMore = followChar(cfg.getGrammar(i).getFirst().charAt(0),x,j+1>=rightGrammar.length()?0:rightGrammar.charAt(j+1));
                    unionChars(more,tmpMore);
                }
            }
            i++;
        }
        return more;
    }

    private static More<Character> followChar(char leftChar, char curChar,char nextChar){
        More<Character> more = new More<>();
        if (curChar==start){
            more.addItem('$');
        }
        if (nextChar==0){
            return follow(leftChar);
        }else{
            More<Character> tmpMore=FIRST.first(cfg,nextChar+"");
            if (tmpMore.containsKey('%')){
                More<Character> foMore = follow(leftChar);
                unionChars(more,foMore);
            }
            tmpMore = removeEpsilon(tmpMore);
            unionChars(more,tmpMore);
        }
        return more;
    }

    private static void unionChars(More<Character> more1, More<Character> more2){
        List<Character> list = more2.getAllItems();
        for (char c : list){
            if (!more1.containsKey(c)){
                more1.addItem(c);
            }
        }
    }

    private static boolean isVn(char c){
        return c>='A'&&c<='Z';
    }

    private static More<Character> removeEpsilon(More<Character> more){
        More<Character> re = new More<>();
        List<Character> list = more.getAllItems();
        for (char c:list){
            if (c!='%'){
                re.addItem(c);
            }
        }
        return re;
    }

}
